package my.code.charpter16;

import java.util.Random;

/**
 * 0-1背包问题：有N 件物品和一个承重为C
 * 的背包（也可定义为体积），每件物品的重量是wi，价值是pi，求解将哪几件物品装入背包可使这些物品在重量总和不超过C 的情况下价值总和最大。
 * 有一个背包，最多能承载重量为C=150的物品，现在有7个物品（物品不能分割成任意大小），编号为1～7，
 * 重量分别是wi=[35,30,60,50,40,10,25]， 价值分别是pi=[10,40,30,50,35,40,30]，现在从这7个物品中选择一个或多个装入背包，
 * 要求在物品总重量不超过C的前提下，所装入的物品总价值最高。
 * 
 * @author xuyuji
 *
 */
public class Main {

	// 进化代数
	public static int MAX_GENERATIONS = 500;

	// 种群大小
	public static int POPULATION_SIZE = 32;

	// 交叉概率
	public static double PC = 0.8;

	// 变异概率
	public static double PM = 0.15;

	// 基因长度
	public static int GENE_SIZE = 7;

	// 最多承受重量
	public static double CAPACITY = 150;

	private int[] Weight = new int[] { 35, 30, 60, 50, 40, 10, 25 };

	private int[] Value = new int[] { 10, 40, 30, 50, 35, 40, 30 };
	
	private Random r = new Random();

	public static void main(String[] args) {
		new Main().evolution();
	}

	private void evolution() {
		Individual[] population = new Individual[POPULATION_SIZE];
		Initialize(population);
		int totalFitness = EnvaluateFitness(population);	//计算适应度
		for (int i = 0; i < MAX_GENERATIONS; i++) {
			population = Select(totalFitness, population);	//选择
			Crossover(population);							//基因交换
			Mutation(population);							//个体变异
			totalFitness = EnvaluateFitness(population);
		}
		printResult(population);
	}

	private void Initialize(Individual[] population) {
		for(int i = 0; i < population.length; i++){
			Individual g = new Individual();
			int gene[] = new int[GENE_SIZE];
			for(int j = 0; j < GENE_SIZE; j++){
				gene[j] = r.nextDouble() > 0.5 ? 1 : 0;
			}
			g.gene = gene;
			population[i] = g;
		}
	}

	private int EnvaluateFitness(Individual[] pop) {
		int totalFitness = 0;
		for (int i = 0; i < POPULATION_SIZE; i++) {
			int tw = 0;
			pop[i].fitness = 0;
			for (int j = 0; j < GENE_SIZE; j++) {
				if (pop[i].gene[j] == 1) {
					tw += Weight[j];
					pop[i].fitness += Value[j];
				}
			}
			if (tw > CAPACITY) /* 惩罚性措施 */ {
				pop[i].fitness = 1;
			}
			totalFitness += pop[i].fitness;
		}
		return totalFitness;
	}

	private Individual[] Select(int totalFitness, Individual[] pop) {
		Individual[] newPop = new Individual[pop.length];
		double lastCf = 0.0;
		// 计算个体的选择概率和累积概率
		for (int i = 0; i < POPULATION_SIZE; i++) {
			pop[i].rf = (double) pop[i].fitness / totalFitness;
			pop[i].cf = lastCf + pop[i].rf;
			lastCf = pop[i].cf;
		}

		for (int i = 0; i < POPULATION_SIZE; i++) {
			double p = r.nextDouble();
			if (p < pop[0].cf) {
				newPop[i] = Individual.valueOf(pop[0]);
			} else {
				for (int j = 0; j < POPULATION_SIZE; j++) {
					if ((p >= pop[j].cf) && (p < pop[j + 1].cf)) {
						newPop[i] = Individual.valueOf(pop[j + 1]);
					}
				}
			}
		}
		
		return newPop;
	}

	private void Crossover(Individual[] pop) {
		int first = -1;//第一个个体已经选择的标识

	    for(int i = 0; i < POPULATION_SIZE; i++)
	    {
	        double p = r.nextDouble();
	        if(p < PC)
	        {
	            if(first < 0)
	            {
	                first = i; //选择第一个个体
	            }
	            else
	            {
	                ExchangeOver(pop, first, i);
	                first = -1;//清除第一个个体的选择标识
	            }
	        }
	    }
	}
	
	private void ExchangeOver(Individual[] pop, int first, int second) {
		/*对随机个数的基因位进行交换*/
	    int ecc = r.nextInt(GENE_SIZE) + 1;
	    for(int i = 0; i < ecc; i++)
	    {
	        /*每个位置被交换的概率是相等的*/
	        int idx = r.nextInt(GENE_SIZE);
	        int tg = pop[first].gene[idx];
	        pop[first].gene[idx] = pop[second].gene[idx];
	        pop[second].gene[idx] = tg;
	    }
	}

	private void Mutation(Individual[] pop) {
		for (int i = 0; i < POPULATION_SIZE; i++) {
			double p = r.nextDouble();
			if (p < PM) {
				ReverseGene(pop, i);
			}
		}
	}

	private void ReverseGene(Individual[] pop, int index) {
		/* 对随机个数的基因位进行变异 */
		int mcc = r.nextInt(GENE_SIZE) + 1;
		for (int i = 0; i < mcc; i++) {
			/* 每个位置被交换的概率是相等的 */
			int gi = r.nextInt(GENE_SIZE);
			pop[index].gene[gi] = 1 - pop[index].gene[gi];
		}
	}
	
	private void printResult(Individual[] population) {
		System.out.println("进化后的种群：");
		int maxFitness = -1;
		for(Individual idd : population){
			if(idd.fitness > maxFitness){
				maxFitness = idd.fitness;
			}
			System.out.println(idd);
		}
		
		System.out.println("适应度最高的个体：");
		for(Individual idd : population){
			if(idd.fitness == maxFitness){
				System.out.println(idd);
			}
		}
	}
}
